#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class Solution 
{
public:
    int trap(vector<int>& height) 
    {
        /* 1、找到数组的最大值的索引 */
        int len = height.size();
        if(len == 0)
            return 0;
        int max = 0;
        for (int i = 1; i < len; i++) // 从1开始
        {
            if (height[i] > height[max])
            {
                max = i;
            }
        }
        

        /* 2、从右到左遍历到最大值 */
        int Left_rainValue = 0;
        int left = 0;
        int right = left + 1;
        int Left_tem = 0;
        while(left < max && right <= max)
        {
            if(height[left] <= height[right])
            {
                Left_rainValue = Left_tem;
                left = right;
                right = left + 1;
                
            }
            else
            {
                Left_tem += (height[left] - height[right]);
                right++;
            }
        }
       
        /* 3、从右到左遍历到最大值 */
        int Right_rainValue = 0;
        int right1 = len - 1;
        int left1 = right1 - 1;
        int Right_tem = 0;
        while(left1 >= max && right1 > max)
        {
            if(height[left1] < height[right1])
            {
                Right_tem += (height[right1] - height[left1]);
                left1--;
            }
            else
            {
                Right_rainValue = Right_tem;
                right1 = left1;
                left1 = right1 - 1;    
                           
            }
        }
       
        return (Left_rainValue + Right_rainValue);
    }

};

int main()
{
    Solution rain;

    vector<int>m_height = {0,1,0,2,1,0,1,3,2,1,2,1};
    cout << "请输入数组：" ;
    while(1)
    {
        int value;
        
        if(cin >> value)
        {
            m_height.push_back(value);
        }
        else 
        {
            break; // 遇到非数字时结束输入
        }
    }

    // 清理输入流
    cin.clear(); // 清除输入错误标志
    // //cin.ignore(numeric_limits<streamsize>::max(), '\n'); // 忽略到行末
    
    cout << "你输入的数组为：";
    for(int i = 0; i < m_height.size(); i++)
    {
        cout << m_height[i] << " ";
    }
    cout << endl;

    cout << "可以接 "<< rain.trap(m_height) << " 单位雨水"<< endl;

    return 0;
}

#if 0
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution 
{
public:
    int trap(vector<int>& height) 
    {
        int len = height.size();
        if (len == 0) return 0;

        int left = 0, right = len - 1;
        int leftMax = 0, rightMax = 0;
        int waterTrapped = 0;

        while (left < right) 
        {
            if (height[left] < height[right]) 
            {
                if (height[left] >= leftMax) 
                {
                    leftMax = height[left];
                } 
                else 
                {
                    waterTrapped += leftMax - height[left];
                }
                left++;
            } 
            else 
            {
                if (height[right] >= rightMax) 
                {
                    rightMax = height[right];
                } 
                else 
                {
                    waterTrapped += rightMax - height[right];
                }
                right--;
            }
        }

        return waterTrapped;
    }
};

int main()
{
    Solution rain;
    vector<int> m_height = {0,1,0,2,1,0,1,3,2,1,2,1};

    // cout << "请输入数组（以非数字结束输入）：" ;
    // while (true)
    // {
    //     int value;
    //     if (cin >> value)
    //     {
    //         m_height.push_back(value);
    //     }
    //     else 
    //     {
    //         break; // 遇到非数字时结束输入
    //     }
    // }

    // 清理输入流
    //cin.clear(); // 清除输入错误标志
    //cin.ignore(numeric_limits<streamsize>::max(), '\n'); // 忽略到行末
    
    cout << "你输入的数组为：";
    for (int i = 0; i < m_height.size(); i++)
    {
        cout << m_height[i] << " ";
    }
    cout << endl;

    cout << "可以接 "<< rain.trap(m_height) << " 单位雨水" << endl;

    return 0;
}
#endif